import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/12 21:57
 * @description 如果一个数为 2 的幂，假设为x , 那么 x & (x-1) = 0, 那么只需要获取 n 上的所有数，然后重新排列，
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.reorderedPowerOf2(1240);
    }
    List<Integer> number = new ArrayList<>();
    boolean can = false;
    boolean[] visited;
    public boolean reorderedPowerOf2(int n) {
        if (check(n)) {
            return true;
        }
        while ( n != 0) {
            number.add(n % 10);
            n /= 10;
        }
        visited = new boolean[number.size()];
        StringBuilder sb = new StringBuilder();
        backTrack(number, 0, sb);
        return can;
    }

    private void backTrack(List<Integer> number, int index, StringBuilder sb) {
        if (index == number.size()) {
            int x = Integer.parseInt(sb.toString());
            can = check(x);
            return;
        }
        if (can) {
            return;
        }
        for (int i = 0; i < number.size(); i++) {
            if (index == 0 && number.get(i) == 0 || visited[i]) {
                continue;
            }
            visited[i] = true;
            sb.append(number.get(i));
            backTrack(number, index + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }

    public boolean check(int x) {
        return (x & (x - 1)) == 0;
    }
}
